COMMENT ⊗   VALID 00005 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	structure of book
C00003 00003	.SEC(LISP - a high-level mathematical language for data structures,Introduction)
C00010 00004	.REQUIRE "NOTES.INT" SOURCE_FILE
C00011 00005	Finally a note on the structure of the text. 
C00012 ENDMK
C⊗;
structure of book
 abstract to specific
 summary and retrospective at end


why?
 show interrelationships of parts of cs
 education and its failures
.SEC(LISP - a high-level mathematical language for data structures,Introduction)

.BEGIN INDENT 20,20;
"... it is important not to lose sight of the fact that there is a difference
between training and education.  If computer science is a fundamental discipline,
then university education in this field should emphasize enduring fundamental
principles rather than transient current technology."
.END
.BEGIN TURN ON"→";
→Peter Wegner, %3Three Computer Cultures%*
.END

This text is nominally about LISP and data structures, however it in fact
covers much broader areas of computer science.
There are two reasons for this more ambitious venture. First the author has long 
felt that the  beginning student of computer science has been getting a distorted 
and disjointed picture of the field. In some ways this confusion is natural; the
field has been growing at such an enourmous rate that few of us are prepared
to be judged experts in all areas of the discipline.  The current alternative
seems to be to give a few introductory courses in programming and machine organization
followed by relatively specialized courses in more technical  areas. 
The difficult with this approach is that much of the technical material
never gets related. The student's perspective and motivation suffers in the
process. This book uses LISP as a means for relating topics which normally
get treated in several  separate  courses. The point is not that we %2can%*
do this in LISP, but rather that it is %2natural%* to do it in LISP.
The high-level notation for algorithms is beneficial in explaining and understanding
complex algorithms.
The use of abstract data structures and abstract LISP programs shows the
true intent of structured programming and step-wise refinement. Much
of the current work in mathematical theories of computation is based on LISP-like
languages. Thus LISP is a formalism for describing algorithms, for writing programs, and
for proving properties of algorithms.
We use data structures as the main thread in our discussions because 
a proper appreciation of data structures as abstract objects is a necessary
prerequisite to an understanding of modern computer science.

Just as it is unnecessary to learn machine language to study numerical
algorithms, it is also unnecessary to learn machine language to understand
non-numerical processes.  The distinction we are making is between data
structures and ⊗→storage structures↔←.  That is, ⊗→data structures↔← are independent
of %6how%* they are implemented on a machine.  Data structures are representations
of information chosen to exhibit certain ordering and accessibility relationships
between data items.  Certainly in the real world you cannot ignore
storage structures when you are deciding upon the data structures which
will encode your problem, but the interesting aspects of representation of
information can be discussed at the level of data structures with no loss
of generality.  The mapping of data structures to storage structures is
machine dependent anyway, and consists of bit-pushing, trickery and black
magic.  We are more interested in ideas than coding tricks.

A very crucial problem in data structures and algorithms is the
interplay between the representation and the algorithm:  if you pick a
frugal representation perhaps your accessing algorithms become more time
consuming or the algorithms become less general.  We will study this
interrelation carefully in this text. We will also see that it is possible,
and most beneficial, to structure our programs such that there is a very
clean interface between the abstract algorithm and the chosen representation.
That is, there will be a set of representation-manipulating programs to test,
select or construct elements of the domain; and there will be a program
encoding the algorithm. To change representations only requires changes
to constructors, selectors and predicates, not to the basic program.

.REQUIRE "NOTES.INT" SOURCE_FILE;

Finally a note on the structure of the text. 
The emphasis  flows from the abstract to the specific, beginning
with a precise description of the domain of LISP functions
and the operations defined over that domain, and  moves to a discussion
of the details of efficient implementation of LISP-like languages.
The practical-minded programmer might be put-off but the "irrelevant"
theory and the theoretical-minded mathematician might be put-off
by the "irrelevant" details of implementation. If you lie somewhere in between
these two extremes, then welcome.